package leetcode;

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {
	public int longestConsecutive(int[] num) {
		Set<Integer> set = new HashSet<Integer>();
		for (int i : num) {
			set.add(i);
		}
		int len = 0;
		for (int i = 0; i < num.length; i++) {
			if (set.contains(num[i])) {
				int next = num[i] - 1; // 找比num[i]小一个的值
				int cnt = 1;
				set.remove(num[i]); // 及时的移除，减少之后的查找时间
				while (set.contains(next)) {
					set.remove(next);
					next--;
					cnt++;
				}
				next = num[i] + 1; // 找比num[i]大一个的值
				while (set.contains(next)) {
					set.remove(next);
					next++;
					cnt++;
				}
				len = Math.max(len, cnt);
			}
		}
		return len;
	}

}
